/*
 * @lc app=leetcode.cn id=528 lang=javascript
 *
 * [528] 按权重随机选择
 */

// @lc code=start
/**
 * @param {number[]} w
 */
var Solution = function(w) {
  let sums = [ w[0] ];
  for (let i = 1; i < w.length; i++) sums[i] = sums[i - 1] + w[i];
  this.sums = sums;
  this.total = sums[sums.length - 1];
};

/**
 * @return {number}
 */
Solution.prototype.pickIndex = function() {
  let sums = this.sums;
  let random = Math.floor(Math.random() * this.total) + 1;

  let head = 0, tail = sums.length - 1;
  while(head < tail) {
    let mid = head + ((tail - head) >> 1);
    if(sums[mid] < random) {
      head = mid + 1;
    } else {
      tail = mid;
    }
  }
  return head;
};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(w)
 * var param_1 = obj.pickIndex()
 */
// @lc code=end

